# Deadlock 
 

# Deadlock (тупик) – это ситуация, когда два или более процесса ожидают друг друга, чтобы завершить свою работу,
# но ни один из них не может продолжить выполнение. Deadlock является одной из наиболее распространенных проблем,
# возникающих в многопоточных, многопроцессорных и асинхронных приложениях.

# Deadlock (тупик) – это режим сбоя параллельности или асинхронности, когда поток или корутины ждут условия, 
# которое никогда не происходит. В результате потоки/корутины, находящиеся в тупике, не могут продвигаться, 
# и программа застревает или замирает и должна быть принудительно завершена.

# Deadlock (тупик) возникает в ситуациях, когда две или более корутины блокируют друг друга, ожидая освобождения 
# ресурсов, захваченных взаимно. В таких условиях каждая корутина оказывается заблокированной, поскольку ресурсы,
# необходимые для её выполнения, удерживаются другими корутинами, что делает невозможным их освобождение и 
# продолжение работы.

# Взаимная блокировка может быть предотвращена с помощью различных стратегий, таких как:

# Иерархия захвата ресурсов;
# Обратный таймаут; 
# Обнаружение и восстановление.

#Тупики не создаются намеренно, они являются неожиданным побочным эффектом или ошибкой в параллельном/асинхронном программировании.

# Общие примеры причин возникновения тупиков корутин включают:
# Корутина, которая ожидает себя (например, пытается получить ту же мьютекс-блокировку дважды).
# Корутины, которые ожидают друг друга (например, A ждет B, B ждет A).
# Корутина, которая не освобождает ресурс (например, мьютекс-блокировка, семафор, барьер, условие, событие и т.д.).
# Корутины, которые получают мьютекс-блокировки в разных порядках (например, не выполняют упорядочение блокировок).
# Тупики могут быть легко созданы, но в действительности их сложно обнаружить в приложении только на основании чтения кода.

# В большинстве случаев Deadlock можно избежать, используя лучшие практики в параллельном программировании, такие как упорядочение блокировок,
# использование тайм-аутов на ожидания и использование менеджеров контекста при получении блокировок.

# Пример Deadlock из реальной жизни:
# Представьте, что четыре автомобиля прибывают на перекрёсток из разных направлений одновременно (см. рисунок ниже).
# Этот перекрёсток особенный — на нём отсутствуют какие-либо светофоры или знаки, которые могут регулировать движение. 
# Также предположим, что все водители строго придерживаются правила, что они должны уступить дорогу тому автомобилю, который прибыл
# на перекрёсток первым.

# Ситуация выглядит следующим образом: каждый водитель видит, что другие автомобили прибыли на перекрёсток в то же время,
# что и он, и поэтому, чтобы соблюсти правила, каждый из них ожидает, пока другие начнут движение. Но поскольку каждый 
# водитель ждёт, никто не начинает движение. Это приводит к ситуации, когда никто не может двигаться, несмотря на то, что все вполне
# способны продолжить движение. 

# Этот сценарий очень похож на те ситуации, которые могут возникнуть в асинхронном программировании, когда две или более
# корутины бесконечно ждут ресурсов, занятых друг другом. Как и в случае с автомобилями на перекрёстке, это может привести
# к состоянию, когда все корутины останавливаются, неспособные продолжить работу.

# ***Пример кода с этим перекрёстком.
# import asyncio


# async def car(lock1, lock2, name):
#     print(f'Автомобиль {name} приближается к перекрестку.')
#     await asyncio.sleep(1)  # Имитация времени приближения к перекрестку

#     async with lock1:
#         print(f'Автомобиль {name} ожидает на перекрестке.')
#         await asyncio.sleep(1)  # Имитация времени ожидания на перекрестке

#         async with lock2:
#             # В реальной ситуации этот код никогда не выполнится из-за deadlock
#             print(f'Автомобиль {name} покидает перекресток.')


# async def main():
#     # Инициализация замков для каждого "направления" движения
#     north_south = asyncio.Lock()
#     east_west = asyncio.Lock()

#     # Запуск асинхронных задач для каждого автомобиля
#     await asyncio.gather(
#         car(north_south, east_west, 'Север-Юг'),
#         car(east_west, north_south, 'Восток-Запад'),
#         car(north_south, east_west, 'Юг-Север'),
#         car(east_west, north_south, 'Запад-Восток')
#     )


# asyncio.run(main())
# Код имитирует приближение автомобилей к перекрестку через задержку в выполнении (await asyncio.sleep(1)).

# Каждый "автомобиль" пытается "захватить" два замка (lock1 и lock2), которые символизируют разрешение на движение через перекресток.
# Первый замок может быть захвачен, но второй ожидает освобождения первого замка другим "автомобилем", что приводит к ситуации взаимной
# блокировки, поскольку каждый "автомобиль" держит один замок и ожидает освобождения другого.

# В результате, ни один из "автомобилей" не сможет покинуть перекресток, так как они заблокированы в ожидании ресурсов, занятых друг другом.
################################################################
# Deadlock: Корутина ждет  сама себя.
# Мы не предполагаем, что этот Deadlock произойдет, например, мы не пишем код намеренно так, чтобы вызвать ожидание корутины самой себя.
# Как правило, это происходит случайно из-за ряда вызовов функций и передачи переменных.

# Корутина может ожидать сама себя по многим причинам, например:
# Ожидание получения мьютекса, который она уже получила.
# Ожидание уведомления о собственном состоянии из самой себя.
# Ожидание установки события самой себе.
# Ожидание освобождения семафора самой себе.
# И так далее.
# Мы можем продемонстрировать тупик, вызванный ожиданием корутины самой себя.

# В этом случае мы разработаем корутину task(), которая напрямую пытается получить ту же мьютекс-блокировку дважды.
# То есть задача получит блокировку, а затем попытается получить блокировку снова.

# Это вызовет тупик, поскольку корутина уже держит блокировку и будет бесконечно ждать, когда она сама освободит блокировку, чтобы снова ее получить.

# import asyncio


# # Корутина, которая дважды получает замок
# async def task(lock):
#     print('Задача пытается захватить замок...')            
    
#     # Захватываем замок
#     async with lock:                                       
#         print('Задача снова пытается захватить замок...')  
        
#         # Снова захватываем замок 
#         # Повторный захват замка приведет к взаимной блокировке, так как замок уже занят той же задачей
#         async with lock:                                   
#             # Сюда мы никогда не дойдем
#             pass


# async def main():
#     # Создаем общий замок
#     lock = asyncio.Lock()                       
#     await task(lock)                            


# asyncio.run(main())  
# При первом захвате замка корутина task() выводит сообщение о своем намерении и успешно получает замок, так как он в этот момент свободен.
# Затем корутина task() пытается снова захватить тот же замок, что приводит к deadlock, поскольку замок уже захвачен и не может быть получен
# повторно. В результате второй блок async with lock: никогда не выполнится.    
##########################################################################
# Deadlock: Корутины ждут друг друга.
# Еще один распространённый тупик - это когда две (или более) корутины ожидают друг друга.

# Корутина A: Ожидает корутину B.
# Корутина B: Ожидает корутину A.
# Или с тремя корутинами вы можете иметь цикл корутин, ожидающих друг друга, например:

# Корутина A: Ожидает корутину B.
# Корутина B: Ожидает корутину C.
# Корутина C: Ожидает корутину A.
# Такой тупик часто встречается, если вы настраиваете корутины на ожидание результата от других корутин, например,
# в конвейере, где некоторые зависимости для подзадач расположены не по порядку.

# Пример приведен ниже.

# Простой пример, иллюстрирующий ситуацию взаимной блокировки (deadlock) между корутинами. В этом примере три корутины (A, B, C) будут 
# # ожидать друг друга в циклическом порядке, как описано выше.
# import asyncio

# async def coroutine_a(event_a, event_b):
#     print("Корутина A: начата")
#     await event_b.wait()
#     print("Корутина A: ожидает корутину B")
#     event_a.set()

# async def coroutine_b(event_b, event_c):
#     print("Корутина B: начата")
#     await event_c.wait()
#     print("Корутина B: ожидает корутину C")
#     event_b.set()

# async def coroutine_c(event_c, event_a):
#     print("Корутина C: начата")
#     await event_a.wait()
#     print("Корутина C: ожидает корутину A")
#     event_c.set()

# async def main():
#     # Создание событий для каждой корутины
#     event_a = asyncio.Event()
#     event_b = asyncio.Event()
#     event_c = asyncio.Event()

#     # Запуск корутин
#     await asyncio.gather(
#         coroutine_a(event_a, event_b),
#         coroutine_b(event_b, event_c),
#         coroutine_c(event_c, event_a),
#     )

# asyncio.run(main())
# event_a, event_b, и event_c - это объекты asyncio.Event(), которые используются для синхронизации корутин.
# Каждое событие служит "флагом",  который ожидает одна корутина и который устанавливается другой.
# Корутина A начинает выполнение, но ожидает событие от корутины B (event_b.wait()), которое не может произойти,
# поскольку корутина B, в свою очередь, ожидает событие от корутины C.
# Аналогично, корутина B ожидает корутину C, а корутина C ожидает корутину A, создавая замкнутый цикл ожидания.

# Тут есть серьезная проблема — возможность взаимной блокировки, или "deadlock". Каждая задача в этом коде ожидает завершения
# другой задачи, которая, в свою очередь, ожидает завершения первой задачи. 

# Это также может произойти при любом типе операций ожидания, когда зависимости корутин создают цикл, например, ожидая
# мьютекс-блокировку, ожидая семафор, ожидая уведомления о состоянии и т.д.

# Ожидание может быть менее очевидным из-за уровня косвенности. Например, корутина может ожидать в очереди, которая сама
# заполняется другой корутиной. В свою очередь другая корутина может ожидать первую корутину напрямую.

# Это может показаться сложным и запутанным, на самом деле так и есть, но помните: не получится понять асинхронность, 
# не пройдя путь знания целиком.

# ***Проблему можно решить, например, путем использования таймаутов, что предотвратит бесконечное ожидание, или путем 
# использования более сложной логики для обработки взаимных зависимостей задач.
# import asyncio

# async def coroutine_a(b_event, c_event):
#     print('Корутина A ожидает B')
#     try:
#         await asyncio.wait_for(b_event.wait(), timeout=2)
#     except asyncio.TimeoutError:
#         print('Корутина A прекратила ожидание B из-за таймаута')
#     c_event.set()  # Сообщаем C, что A завершила ожидание
#     print('Корутина A завершила выполнение')

# async def coroutine_b(a_event, c_event):
#     print('Корутина B ожидает C')
#     try:
#         await asyncio.wait_for(c_event.wait(), timeout=2)
#     except asyncio.TimeoutError:
#         print('Корутина B прекратила ожидание C из-за таймаута')
#     a_event.set()  # Сообщаем A, что B завершила ожидание
#     print('Корутина B завершила выполнение')

# async def coroutine_c(b_event, a_event):
#     print('Корутина C ожидает A')
#     try:
#         await asyncio.wait_for(a_event.wait(), timeout=2)
#     except asyncio.TimeoutError:
#         print('Корутина C прекратила ожидание A из-за таймаута')
#     b_event.set()  # Сообщаем B, что C завершила ожидание
#     print('Корутина C завершила выполнение')

# async def main():
#     # Инициализируем события для управления ожиданием корутин
#     a_event = asyncio.Event()
#     b_event = asyncio.Event()
#     c_event = asyncio.Event()

#     # Запускаем корутины
#     await asyncio.gather(
#         coroutine_a(b_event, c_event),
#         coroutine_b(a_event, c_event),
#         coroutine_c(b_event, a_event),
#     )

# asyncio.run(main())

# Каждая корутина ожидает событие от другой корутины, но с введением таймаута через asyncio.wait_for.
# Это предотвращает бесконечное ожидание в случае взаимной блокировки.
# После истечения таймаута корутина перестает ожидать и продолжает выполнение, устанавливая событие для 
# следующей корутины в цепочке, что обеспечивает возможность продвижения вперед даже в случае взаимной блокировки.
# Таким образом, используя таймауты и события, мы обрабатываем взаимные зависимости задач, предотвращая
# бесконечное ожидание и обеспечивая завершение работы всех корутин.
###########################################
###########################################
# Deadlock: Корутины получают блокировки в неправильном порядке:
# Обычной причиной такого тупика является то, что две корутины получают блокировки в разном порядке одновременно.

# Например, у нас может быть критический участок, защищенный блокировкой, и внутри этого критического участка у нас может
# быть код или вызов функции, который защищен второй блокировкой.

# Мы можем столкнуться с ситуацией, когда одна корутина получает lock1, затем пытается получить lock2 , а другая корутина,
# которая вызывает функциональность lock2, затем пытается получить lock1. Если это происходит одновременно, когда coroutine1
# удерживает lock1, а coroutine2 удерживает lock2, то будет тупик.
# Coroutine1: Удерживает lock1, ожидает lock2.
# Coroutine2: Удерживает lock2, ожидает lock1.

# Мы можем создать корутину task(number, lock1, lock2), которая принимает число и обе блокировки в качестве аргументов, а затем
# пытается получить первую блокировку, а затем вторую блокировку. Затем могут быть созданы две корутины с блокировками в 
# качестве аргументов, но, возможно, мы допустили опечатку и у нас первая корутина принимает lock1, а затем lock2 в качестве аргументов,
# а вторая корутина принимает lock2, а затем lock1 в качестве аргументов.
# Результатом будет тупик, если каждая корутина сможет сначала получить блокировку, а затем ожидать вторую блокировку.

# Пример кода приведен ниже:
# import asyncio

# async def task(number, first_lock, second_lock):
#     print(f"Задача {number}: пытается захватить первую блокировку")
#     async with first_lock:
#         print(f"Задача {number}: захватила первую блокировку")
#         await asyncio.sleep(1)  # Имитация работы в критическом участке
#         print(f"Задача {number}: пытается захватить вторую блокировку")
        
#         async with second_lock:
#             print(f"Задача {number}: захватила вторую блокировку")
#             await asyncio.sleep(1)  # Дополнительная работа в критическом участке
#     print(f"Задача {number}: завершила выполнение")

# async def main():
#     # Инициализация двух асинхронных блокировок
#     lock1 = asyncio.Lock()
#     lock2 = asyncio.Lock()

#     # Запуск корутин с блокировками в разном порядке
#     await asyncio.gather(
#         task(1, lock1, lock2),
#         task(2, lock2, lock1),
#     )

# asyncio.run(main())

# Две корутины task(1, lock1, lock2) и task(2, lock2, lock1) запускаются одновременно.
# task(1, lock1, lock2) пытается захватить lock1, затем lock2.
# task(2, lock2, lock1) пытается захватить lock2, затем lock1.
# Если task(1) захватывает lock1, а task(2) захватывает lock2 до того, как другая корутина освободит свою блокировку, 
# возникает взаимная блокировка. Обе корутины ожидают освобождения блокировки другой корутиной, что приводит к тупику,
# и они не могут продолжить выполнение.

# Решением является гарантирование того, что блокировки всегда получаются в одном и том же порядке во всей программе.

# ***Решением является гарантирование того, что блокировки всегда получаются в одном и том же порядке во всей программе.

import asyncio

async def task(number, locks):
    # Определяем порядок захвата блокировок по их идентификаторам
    sorted_locks = sorted(locks, key=id)

    print(f"Задача {number}: пытается захватить блокировки в порядке {sorted_locks}")
    async with sorted_locks[0]:
        async with sorted_locks[1]:
            print(f"Задача {number}: захватила обе блокировки")
            await asyncio.sleep(1)  # Имитация работы в критическом участке
    print(f"Задача {number}: завершила выполнение")

async def main():
    # Инициализация двух асинхронных блокировок
    lock1 = asyncio.Lock()
    lock2 = asyncio.Lock()

    # Запуск корутин с блокировками, передаваемыми в разном порядке, но захватывающимися в одном и том же порядке
    await asyncio.gather(
        task(1, [lock1, lock2]),
        task(2, [lock2, lock1]),
    )

asyncio.run(main())
# Вывод:

# Задача 1: пытается захватить блокировки в порядке [<asyncio.locks.Lock object at 0x000002D9C71EDCD0 [unlocked]>, <asyncio.locks.Lock object at 0x000002D9C7228BC0 [unlocked]>]
# Задача 1: захватила обе блокировки
# Задача 2: пытается захватить блокировки в порядке [<asyncio.locks.Lock object at 0x000002D9C71EDCD0 [locked]>, <asyncio.locks.Lock object at 0x000002D9C7228BC0 [locked]>]
# Задача 1: завершила выполнение
# Задача 2: захватила обе блокировки
# Задача 2: завершила выполнение
# Мы определяем функцию task(), которая принимает номер задачи и список блокировок. Вместо того чтобы пытаться захватить блокировки в порядке,
# в котором они были переданы, задача сортирует блокировки по их уникальному идентификатору с помощью sorted(locks, key=id). Это гарантирует,
# что блокировки всегда захватываются в одном и том же порядке, независимо от порядка, в котором они были переданы в функцию.

# Каждая корутина task() пытается захватить обе блокировки, начиная с блокировки с наименьшим идентификатором. Это предотвращает взаимную блокировку,
# так как невозможна ситуация, когда одна корутина держит первую блокировку и ожидает вторую, в то время как другая держит вторую и ожидает первую.

# Даже если корутины получают блокировки в разном порядке, использование сортированного списка гарантирует, что порядок захвата блокировок будет
# одинаковым, предотвращая взаимную блокировку.
######################################################

# Deadlock: Ошибка при освобождении блокировки.
# Еще одной общей причиной тупика является невыполнение корутиной обязанности освободить ресурс.

# Обычно это вызвано тем, что корутина вызывает ошибку или исключение в критическом разделе, что мешает корутине освободить ресурс.

# Некоторые примеры ошибки освобождения ресурса:

# Неудача при освобождении блокировки (lock*).
# Неудача при освобождении семафора (semaphore*).
# Неудача при достижении барьера (barrier*).
# Неудача при оповещении корутин об условии (condition*).
# Неудача при установке события (event*).
# И так далее.

# Мы можем продемонстрировать этот тупик на примере.

# Корутина может получить блокировку для выполнения критического раздела, затем вызвать исключение, которое мешает корутине освободить блокировку. 
# Другая корутина может затем попытаться получить ту же блокировку и должна ждать вечно, так как блокировка никогда не будет освобождена,
# что приводит к тупику.

# Пример кода приведен ниже.

# import asyncio



# async def task(lock):                           
#     print('Задача приобретает блокировку...')   
#     # Приобретаем блокировку
#     await lock.acquire()         

#     # Генерируем исключение, симулируя ошибку               
#     raise Exception('Произошло что-то плохое')  
    
#     # освобождаем блокировку (сюда никогда не дойдем)
#     print('Задача освобождает блокировку...')   
    
#     # Так как перед этим есть исключение, то этот код никогда не будет выполнен
#     lock.release()                              


# async def main(): 
#     lock = asyncio.Lock()                                
#     asyncio.create_task(task(lock))                      
#     await asyncio.sleep(1)                               
#     print('Основная функция приобретает блокировку...')  
#     # Используем метод acquire() для асинхронного приобретения блокировки
#     await lock.acquire()                                 
    
#     # освобождаем блокировку (сюда никогда не дойдем)
#     # Освобождаем блокировку методом release(). 
#     # Но этот код не будет выполнен, так как предыдущий вызов acquire() не будет завершен, поскольку задача, 
#     # которая первоначально приобрела блокировку, не освободила ее из-за ошибки
#     lock.release()                                     


# asyncio.run(main())
################################################
# Советы по предотвращению Deadlock
# Несколько простых советов могут вам значительно помочь.

# Используйте конструкцию try/finally.
# Используйте менеджеры контекста при захвате и освобождении блокировок with.
# Используйте таймауты при ожидании.
# Всегда захватывайте блокировки в одном и том же порядке.

# Используйте менеджеры контекста.
# Приобретайте и освобождайте блокировки с помощью менеджера контекста, где это возможно.

# Блокировки можно получить вручную с помощью вызова acquire() в начале критического участка, а затем вызова release() в конце критического участка.

# Например:
# приобретаем блокировку вручную
# lock.acquire()  


# # освобождаем блокировку
# lock.release()  

# Традиционно рекомендуется всегда приобретать и освобождать блокировку в структуре try/finally.

# Когда блокировка получена, критический участок выполняется в блоке try, и  блокировка всегда освобождается в блоке finally.

# Например:
# приобретаем блокировку
# lock.acquire()  

# try:
#     # Критический участок кода...
#     # Здесь выполняется код, который требует синхронизации доступа. 
#     # Когда блокировка устанавлена, никакая другая корутина не может получить доступ к этому участку кода.
# finally:
#     # всегда освобождаем блокировку
#     lock.release()  

#     Менеджер контекста позволяет сделать то же самое с меньшим количеством кода.
# Например:

# # Конструкция with автоматически устанавливает и освобождает блокировку. 
# async with lock:  
#     # критический участок кода...
#     # Здесь выполняется код, который требует синхронизации доступа. 
#     # Когда блокировка приобретена, никакая другая корутина не может получить доступ к этому участку кода.
# Преимущество менеджера контекста заключается в том, что блокировка всегда освобождается, как только выходит из блока, независимо 
# от того, как она происходит, например, нормальный возврат, ошибка возврата или исключение.

# Используйте тайм-ауты при ожидании.
# Всегда используйте таймаут при ожидании завершения корутины или задачи.

# Мы должны использовать функцию asyncio.wait_for(), чтобы ожидать выполнение корутины или задачи с таймаутом. 

# try:
#     # Пытаемся приобрести блокировку, ожидая не более 10 секунд

#     # Метод wait_for() asyncio используется для ограничения времени ожидания при попытке приобретения блокировки. 
#     # Это полезно в случаях, когда блокировка может быть не освобождена длительное время, и мы не хотим, 
#     # чтобы наш код заблокировался навсегда, ожидая приобретения блокировки.
    
#     await asyncio.wait_for(lock.acquire(), timeout=10)  
# except asyncio.TimeoutError:
#     # здесь обрабатываем ситуацию, когда время ожидания истекло
#     # ... 
# Это позволит ожидающей корутине прекратить ожидание после фиксированного временного лимита, а
# затем попытаться исправить ситуацию, например, сообщить об ошибке, принудительно завершить выполнение и т.д.